//给定不同面额的硬币 coins 和一个总金额 amount。编写一个函数来计算可以凑成总金额所需的最少的硬币个数。如果没有任何一种硬币组合能组成总金额，返回
// -1。 
//
// 
//
// 示例 1: 
//
// 输入: coins = [1, 2, 5], amount = 11
//输出: 3 
//解释: 11 = 5 + 5 + 1 
//
// 示例 2: 
//
// 输入: coins = [2], amount = 3
//输出: -1 
//
// 
//
// 说明: 
//你可以认为每种硬币的数量是无限的。 
// Related Topics 动态规划 
// 👍 709 👎 0

package leetcode.editor.cn;

import common.util.MyUtil;

import java.util.HashMap;
import java.util.Map;

/**
 * Java：零钱兑换
 *
 * @author changgui
 */
@SuppressWarnings("all")
public class P322_CoinChange {
    public static void main(String[] args) {
        Solution solution = new P322_CoinChange().new Solution();
        // TODO 此处开始你的表演
        int[] nums = MyUtil.createArray(1, 2, 5);
        MyUtil.print(solution.coinChange(nums, 100));

    }

    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {

        public int coinChange(int[] coins, int amount) {
            Map<Integer, Integer> map = new HashMap<>(amount);
            //int[] arr = new int[amount + 1];
            //for (int i = 0; i < arr.length; i++) {
            //    arr[i] = -2;
            //}
            return coinChange(map, coins, amount);
        }

        public int coinChange(Map<Integer, Integer> map, int[] coins, int amount) {
            if (amount == 0) {
                return 0;
            }
            if (amount < 0) {
                return -1;
            }
            int res = Integer.MAX_VALUE;
            for (int coin : coins) {
                Integer count = map.get(amount - coin);
                if (count == null) {
                    count = coinChange(map, coins, amount - coin);
                    map.put(amount - coin, count);
                }
                if (count == -1) {
                    continue;
                }
                res = Math.min(res, count + 1);
            }
            return res == Integer.MAX_VALUE ? -1 : res;
        }

    }
    //leetcode submit region end(Prohibit modification and deletion)

}
